Low Density Parity Check (LDPC) coding is an Error Correction Code (ECC) technique that is being increasingly regarded as a valid alternative to Turbo Codes. LDPC codes have been incorporated into the specifications of several real systems, and the LDPC decoder may turn out to constitute a significant portion of the corresponding digital transceiver.
Non-Binary Low Density Parity Check (LDPC) codes are defined by a sparse parity check matrix H in a finite Galois field GF(2p). The check matrix H include a number M of rows, equal to the number of parity check nodes, and a number N of columns, equal to the number of symbols of each received word (codeword). The value of each symbol of a codeword belongs to the Galois field GF(2p) and is represented by a string of p bits.
Every valid codeword c that may be transmitted satisfies the following check equation in the Galois field GF(2p): H· c= 0with c being a column vector and 0 a null column vector, whilst invalid codewords do not satisfy it. More specifically, the code is described by a set of j=0, . . . nc−1 parity check equations:
            ∑              i        ∈                  VC          ⁡                      (            j            )                                ⁢                  H        ji            ·              c        i              =            0      ⇒                        H                      _            _                          ·                  c          _                      =    0  where both the codeword symbols ci and the parity check coefficients Hji belong to the GF(2p) and VC(j) is the set of variables (symbols ci) involved in the j-th check.
The transmitter transmits a valid codeword c over a noisy channel. Alternatively, the valid codeword can be written on a storage support (like the magnetic disk of a Hard Disk Drive). The receiver receives a noisy and distorted signal r representing a stream of symbols c. The receiver is capable of delivering a first probabilistic estimate of the transmitted symbols through the PMF (Probability Mass Function) by means of a demodulator or a detector that are not part of the invention. The PMF are the probability that a received symbol Xi is equal to one of the possible symbol over GF(2p): P(Xi=φq) φq εGF(2p). The stream of most likely received symbols is x=[{circumflex over (X)}0, {circumflex over (X)}1, . . . {circumflex over (X)}N]
            X      ^        i    =            argmax      q        ⁢                  P        ⁡                  (                                    X              i                        =                          φ              q                                )                    .      
As contemplated in LDPC coding, the product of the check matrix H by the received word x is performed. Because of noise and channel distortion, the result of this product is generally not the null vector: H· x= z≠ 0thus the receiver may determine which codeword has been received by implementing an appropriate decoding technique based on properties of LDPC codes. The a posteriori probability that a codeword c has been transmitted when a generic signal r has been received is computed taking into account the code constraint.
More specifically, LDPC are decoded by means of a belief propagation algorithm that is described in the following paragraphs. The symbols are characterized by the PMF (Probability Mass Function). In the preferred embodiment PMF are represented in the log-domain:Λiq=−log(P(Xi=φq)) φqεGF(2p)
Using the vector representationΛi=└Λi0,Λi1, . . . Λiq-1┘
The full complexity algorithm to be used as reference is the log-domain symbol based belief propagation and is calculated as
                    Λ        iq            =                                    -                          log              ⁡                              (                                  P                  ⁡                                      (                                                                  X                        i                                            =                                              φ                        q                                                              )                                                  )                                              ⁢                                          ⁢                      ∀            i                          =        0              ,                  …        ⁢                                  ⁢        nv        ⁢                                  ⁢                  ∀          q                    =      0        ,                  …        ⁢                                  ⁢                  2          p                    -      1                          ⁢                  for        ⁢                                  ⁢        k            =              1        :                  N          ite                                        ⁢                  for        ⁢                                  ⁢        j            =              1        :        nc                                ⁢                  for        ⁢                                  ⁢        i            ∈              VC        ⁡                  (          j          )                                        ⁢                            Q          ij                =                                            Λ              i                        -                                          R                ji                            ⁢                              ∀                q                                              =          0                    ,                        …          ⁢                                          ⁢                      2            p                          -        1                                ⁢                            R          ji                =                                            SPC              ⁡                              (                                                      H                    j                                    ,                                      Q                    ij                                                  )                                      ⁢                          ∀              q                                =          0                    ,                        …          ⁢                                          ⁢                      2            p                          -        1                                ⁢                  Λ        i            =                        Q          ij                +                  R          ji                                        X        ^            i        =                  argmax        q            ⁡              (                  Λ          iq                )            where Qij, Rji represent the variable to check and the check to variable messages (vectors each including a single PMF relative to the i-th symbol). In a preferred embodiment the belief propagation is implemented with the layered schedule (Dale E. Hocevar, “A reduced complexity decoder architecture via layered decoding of LDPC Codes”, IEEE Workshop on Signal Processing Systems (SIPS), October 2004, pp. 107-112).
The check node processing (CNP) is performed by the SPC function. This is the most computational intensive part of the decoding algorithm. It is worth reviewing the approaches proposed so far for the decoding of Non Binary LDPC.
M. C. Davey and D. MacKay, “Low-density parity-check codes over GF(q)”, IEEE Commun. Lett., vol. 2, no. 6, pp. 165, that first introduced the use of Non binary LDPC, proposed a very general implementation of the belief propagation (called also Sum Product Algorithm). It works in the probability domain. It has been noted very soon that this it has stability problems when probability values are represented in finite digit. Moreover, its complexity increases as the square of the size of the Galois field 2p.
Henk Wymeersch, Heidi Steendam and Marc Moeneclaey “Log-domain decoding of LDPC codes over GF (q)” Proc. IEEE International Conference on Communications, proposed the Sum Product Algorithm in logarithm domain. Its complexity increases as the square of the size of the Galois field 2p. The log domain is the preferred embodiment also for the present invention.
H. Song and J. R. Cruz, Reduced-complexity decoding of q-ary LDPC codes for magnetic recording,” IEEE Trans. Magn., vol. 39, no. 2, pp. 1081, introduced the SPC processing with the forward-backward approach describe below. Moreover they proposed Q-ary LDPC decoding using Fast Fourier Transform (FFT), both in probability and in logarithm domains. Unfortunately, probability domain gives instability problem when finite representation is used and the FFT in the logarithm domain involves doubling the used quantities. The advantage of using FFT approach is therefore is lost.
A. Voicila, D. Declereq, F. Verdier, M. Fossorier, P. Urard, “Low-complexity, Low-memory EMS algorithm for non-binary LDPC codes” IEEE International Conference on Communications, 2007, ICC '07, proposed the so-called Extended Min Sum algorithm: this very generic approach introduces the concept of reduction of candidates at the input of the SPC but does not provide a computationally simple and effective way to perform the CNP.
Therefore, there is the need for a simpler and faster algorithm usable for decoding non-binary LDPC codes, especially in the most computationally intensive part that is the SPC.
The exact formulation of the SPC is the following:
      R    jip    =            SPC      ⁡              (                              H            j                    ,                      Q            ij                          )              =                            -                      log            ⁡                          (                              P                ⁡                                  (                                                            X                      i                                        =                                          φ                      p                                                        )                                            )                                      ⁢                                  ⁢                  s          .          t          .                                          ⁢                                    ∑                              i                ∈                                  VC                  ⁡                                      (                    j                    )                                                                        ⁢                                          H                ji                            ⁢                              X                i                                                        =      0      
The straight-forward approach to solve the SPC is based on the forward-backward recursion over a fully connected trellis with q=2p states (see for example H. Song and J. R. Cruz, Reduced-complexity decoding of q-ary LDPC codes for magnetic recording,” IEEE Trans. Magn., vol. 39, no. 2, pp. 1081 where the same approach is introduce in the probability domain).
States correspond to the symbols Xi. The branches are given by Qijp and the state connections are determined by the parity check coefficients.
The forward recursion for a generic parity check equation with coefficients Ht where the inputs PMF are Qtp=−log(Pin(Xt=φp) is given by:
            a      i        ⁡          (      z      )        =                    -        log            ⁢                          ⁢              (                  P          ⁡                      (                                          state                t                            =                              φ                z                                      )                          )              =                  max                              n            =            0                    ,                                          ⁢                                    …              ⁢                                                          ⁢              q                        -            1                              ⁢              *                  (                                                    a                                  t                  -                  1                                            ⁡                              (                n                )                                      -                          log              ⁡                              (                                                      P                                          i                      ⁢                                                                                          ⁢                      n                                                        ⁡                                      (                                                                  X                        t                                            =                                                                        H                          t                                                      -                            1                                                                          ·                                                  (                                                                                    φ                              z                                                        -                                                          φ                              n                                                                                )                                                                                      )                                                  )                                              )                    
Backward recursion is defined analogously. The combining step is given by
      R    tz    =            -              log        ⁡                  (                      P            ⁡                          (                                                X                  t                                =                                  φ                  z                                            )                                )                      =                            max                                                    n                =                0                            ,                                                          ⁢                                                …                  ⁢                                                                          ⁢                  q                                -                1                                                                    m                =                0                            ,                                                          ⁢                                                …                  ⁢                                                                          ⁢                  q                                -                1                                                    ⁢                  *                      (                                                            a                                      t                    -                    1                                                  ⁡                                  (                  n                  )                                            +                                                β                                      t                    +                    1                                                  ⁡                                  (                  m                  )                                                      )                    ⁢                                          ⁢                      s            .            t            .                                                  ⁢                                          H                t                                  -                  1                                            ⁡                              (                                                      φ                    n                                    +                                      φ                    m                                                  )                                                        =              φ        z            
The straightforward approximation available at the Check Node Processing is the substitution of the max* operator with the max. In order to compensate the well-known overestimation of the max operator a proper scaling factor is applied at the SPC output so that the recursion is given by:
            a      t        ⁡          (      z      )        =            max                        n          =          0                ,                                  ⁢                              …            ⁢                                                  ⁢            q                    -          1                      ⁢          (                                    a                          t              -              1                                ⁡                      (            n            )                          -                  log          ⁡                      (                                          P                                  i                  ⁢                                                                          ⁢                  n                                            ⁡                              (                                                      X                    t                                    =                                                            H                      t                                              -                        1                                                              ·                                          (                                                                        φ                          z                                                -                                                  φ                          n                                                                    )                                                                      )                                      )                              )      and the combining is
      R    tz    =            γ      ·                        max                                                    n                =                0                            ,                                                          ⁢                                                …                  ⁢                                                                          ⁢                  q                                -                1                                                                    m                =                0                            ,                                                          ⁢                                                …                  ⁢                                                                          ⁢                  q                                -                1                                                    ⁢                              (                                                            a                                      t                    -                    1                                                  ⁡                                  (                  n                  )                                            +                                                β                                      t                    +                    1                                                  ⁡                                  (                  m                  )                                                      )                    ⁢                                          ⁢                      s            .            t            .                                                  ⁢                                          H                t                                  -                  1                                            ⁡                              (                                                      φ                    n                                    +                                      φ                    m                                                  )                                                          =          φ      z      where the scaling factor γ is—in the context of magnetic recording—about 0.75.
This algorithm is the natural extension of the normalized min-sum belief propagation in the binary field (Zarkeshvari, F.; Banihashemi, A. H.; “On implementation of min-sum algorithm for decoding low-density parity-check (LDPC) codes”, Global Telecommunications Conference, 2002. GLOBECOM '02. IEEE Volume 2, 17-21 November 2002 Page(s): 1349-1353.).
In order to further simplify the decoding algorithm, both input and SPC processing can be restricted to a subset of symbol candidates (A. Voicila, D. Declereq, F. Verdier, M. Fossorier, P. Urard, “Low-complexity, Low-memory EMS algorithm for non-binary LDPC codes” IEEE International Conference on Communications, 2007, ICC '07).